package algorithm.tree;

import algorithm.NodeParent;

/**
 * 中序遍历后继节点
 *
 * @author csp 2021-12-18
 */
public class Code06_InSortSuccessorNode {

    /**
     * 1) X有右树，X的后继为右树的最左节点
     * 2）X无右树。
     *
     */

    public static NodeParent getSuccessorNode(NodeParent node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node);
        } else {
            NodeParent parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }


    public static NodeParent getLeftMost(NodeParent node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;

    }
    // 树的序列化和反序列化
    // 贪心
}
